import java.text.DecimalFormat;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class HeapSort {
    /*将array[a]和array[b]、array[c]中最大值进行比较，如果较小则将array[a]与array[b]、array[c]中最大值
    进行交换，否则直接返回数组array*/
    public static int[] getMaxA(int[] array,int a,int b ,int c){
        int temp = 0;
        if(array[b] >= array[c]){
            if(array[a] < array[b]){
                temp = array[a];
                array[a] = array[b];
                array[b] = temp;
                for(int k=1;k<array.length;k++){
                    System.out.print(array[k]+" ");
                }
                System.out.println();
            }
        }
        else{
            if(array[a] < array[c]){
                temp = array[a];
                array[a] = array[c];
                array[c] = temp;
                for(int k=1;k<array.length;k++){
                    System.out.print(array[k]+" ");
                }
                System.out.println();
            }
        }
        return array;
    }

    //根据堆排序父母优势规则，返回一个给定长度的数组的成堆结果
    public static int[] getHeapSort(int[] array , int len){
        boolean judge = true;
        System.out.println("处理过程：");
        for(int k=1;k<array.length;k++){
            System.out.print(array[k]+" ");
        }
        System.out.println();
        while(judge){
            //根据堆排序父母优先规则，对数组array进行排序
            for(int i = len/2;i >=1;i--){
                if((2*i+1) < len){
                    array = getMaxA(array,i,(2*i),(2*i+1));
                }
                if((2*i) == len-1){    //当2*i == len-1时，说明array[i]只有一个左孩子节点a[2*i]
                    int temp = 0;
                    if(array[i] < array[2*i]){
                        temp = array[i];
                        array[i] = array[2*i];
                        array[2*i] = temp;
                        for(int k=1;k<array.length;k++){
                            System.out.print(array[k]+" ");
                        }
                        System.out.println();
                    }
                }
            }

            //遍历数组array，一旦出现根节点小于其叶子节点时，跳出for循环
            int j;
            for(j = 1;j < len/2;j++){
                if((2*j+1) < len){
                    if(array[j] < array[2*j]){
                        break;
                    }
                    if(array[j] < array[2*j+1]){
                        break;
                    }
                }
                if((2*j) == len-1){
                    if(array[j] < array[2*j]){
                        break;
                    }
                }
            }

            if(j == len/2) { //如果j==len/2，说明遍历结果符合堆排序规则，直接结束while循环
                judge = false;
            }
        }
        return array;
    }

    //使用数组成堆，对一个数组元素进行从小到大排序，并返回排序后的结果
    public static int[] getResultSort(int[] array , int len){
        array =  getHeapSort(array , len);           //首先对数组进行堆排序处理
        System.out.println("堆排序之后的数组为：");
        for(int k=1;k<array.length;k++){
            System.out.print(array[k]+" ");
        }
        return array;
    }

    //删除最大键
    public static void DeleteMax(int[] array,int len){
        int temp=0;
        if(len>1){
            if(len>1){
                for (int i=1;i<len;i++){
                    System.out.print(array[i]+" ");
                }
                System.out.println();
            }


            temp=array[1];
            array[1]=array[len-1];
            array[len-1]=temp;

            if(len>1){
                for (int i=1;i<len;i++){
                    System.out.print(array[i]+" ");
                }
                System.out.println();
            }

            len=len-1;
            array=getResultSortt(array,len);

            DeleteMax(array,len);
            System.out.println();
        }
    }

    public static int[] getMaxAt(int[] array,int a,int b ,int c){
        int temp = 0;
        if(array[b] >= array[c]){
            if(array[a] < array[b]){
                temp = array[a];
                array[a] = array[b];
                array[b] = temp;
            }
        }
        else{
            if(array[a] < array[c]){
                temp = array[a];
                array[a] = array[c];
                array[c] = temp;
            }
        }
        return array;
    }

    public static int[] getHeapSortt(int[] array , int len){
        boolean judge = true;

        while(judge){
            //根据堆排序父母优先规则，对数组array进行排序
            for(int i = len/2;i >=1;i--){
                if((2*i+1) < len){
                    array = getMaxAt(array,i,(2*i),(2*i+1));
                }
                if((2*i) == len-1){    //当2*i == len-1时，说明array[i]只有一个左孩子节点a[2*i]
                    int temp = 0;
                    if(array[i] < array[2*i]){
                        temp = array[i];
                        array[i] = array[2*i];
                        array[2*i] = temp;
                    }
                }
            }

            //遍历数组array，一旦出现根节点小于其叶子节点时，跳出for循环
            int j;
            for(j = 1;j < len/2;j++){
                if((2*j+1) < len){
                    if(array[j] < array[2*j]){
                        break;
                    }
                    if(array[j] < array[2*j+1]){
                        break;
                    }
                }
                if((2*j) == len-1){
                    if(array[j] < array[2*j]){
                        break;
                    }
                }
            }

            if(j == len/2) { //如果j==len/2，说明遍历结果符合堆排序规则，直接结束while循环
                judge = false;
            }
        }
        return array;
    }


    public static int[] getResultSortt(int[] array , int len){
        array =  getHeapSortt(array , len);           //首先对数组进行堆排序处理
        return array;
    }



    public static void main(String args[]){
        Scanner in = new Scanner(System.in);

        System.out.println("请输入待处理数组个数个数：");
        int n = in.nextInt();
        int[] array=new int[n+1];
        System.out.println("请依次输入数值：");
        for (int i = 1; i < n+1; i++) {
            array[i] = in.nextInt();
        }

        int len = array.length;
        int[] result = getResultSort(array,len);
        System.out.println();

        System.out.println("删除最大键过程：");
        DeleteMax(result,len);
    }
}